#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution
{
public:
    int maximumRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget)
    {
        int left = 0;
        int maxCount = 0;
        long long summary = 0;
        deque<int> que;
        for (int right = 0; right < runningCosts.size(); right++)
        {
            while (!que.empty() && que.back() < chargeTimes[right])
                que.pop_back();
            que.push_back(chargeTimes[right]);
            summary += runningCosts[right];

            while (!que.empty() && budget < que.front() + (right - left + 1) * summary)
            {
                summary -= runningCosts[left];
                if (que.front() == chargeTimes[left])
                    que.pop_front();
                left++;
            }

            maxCount = max(maxCount, right - left + 1);
        }
        return maxCount;
    }
};

int main()
{
    cout << "Code2398" << endl;
    Solution s;
    // vector<int> chargeTime = {3, 6, 1, 3, 4};
    // vector<int> runingCost = {2, 1, 3, 4, 5};
    // int budget = 25;
    vector<int> chargeTime = {11, 12, 19};
    vector<int> runingCost = {10, 8, 7};
    int budget = 19;
    cout << s.maximumRobots(chargeTime, runingCost, budget);
    return 0;
}